 import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        quickSort(a);
        return a[n-K];
    }
    //快速排序

    //parttion 的Hoare法

    private static int parttion(int[]array,int start,int end){

        int pivot=array[start];
        int leftIdx=start;
        int rightIdx=end;
        while(leftIdx<rightIdx){
            //右边都要大于基准值pivot
            while(leftIdx<rightIdx&&array[rightIdx]>=pivot){
                rightIdx--;
                //此循环结束代表找到了小于pivot的值
            }
            //左边都要小于基准值pivot
            while(leftIdx<rightIdx&&array[leftIdx]<=pivot){
                leftIdx++;
                //此循环结束代表找到了大于pivot的值
            }
            //将大于的于小于的交换位置
            swap(array,leftIdx,rightIdx);

        }
        //大循环结束，左右相遇，将pivot再放回到大于于小于的中间
        swap(array,start,leftIdx);
        //返回基准值的下标
        return leftIdx;

    }
    //交换两个数的值
    private static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    private static void quickSort(int[]arr){
        quickSortRange(arr,0,arr.length-1);
    }
    private static void quickSortRange(int[]arr,int fromIdx,int toIdx){
        //计算左右区间里的元素个数
        int size=toIdx-fromIdx+1;
        if(size<=1){
            //当元素个数小于或等于1退出递归
            return;
        }
        int pivotIdx=parttion(arr,fromIdx,toIdx);
        quickSortRange(arr,fromIdx,pivotIdx-1);
        quickSortRange(arr,pivotIdx+1,toIdx);
    }
}